//
//  BTree.hpp
//  BTree
//
//  Created by chenyh on 2021/2/18.
//

#ifndef BTree_hpp
#define BTree_hpp

#include <iostream>

template<typename DataType> class BTree
{
public:
    BTree()
    {
        root = NULL;
    }
    ~BTree()
    {
        //clear() // 清楚b树
    }
private:
    static const int t = 2;//b树的最小度数
    static const int Key_Max = 2*t-1;//结点中包含的关键字的最大个数
    static const int Key_Min = t - 1;//结点中包含的关键字的最小个数
    static const int Child_Max = Key_Max+1;//孩子结点的最大个数
    static const int Child_Min = Key_Min+1;//孩子结点的最小个数
    template<class T> struct Node
    {
        bool isLeaf;
        int Key_Num;    //结点包含的关键字的个数
        DataType keyArray[Key_Max]; //关键字数组
        Node<DataType> *pChild[Child_Max];//子树指针数组
        Node<DataType>(bool b=true,int n=0):isLeaf(b),Key_Num(n){}
    };
    Node<DataType> *root;//b树根结点
public:

    /**b树的搜索*/
    template<class T> struct SearchResult
    {//搜索操作返回关键字所在结点和序列
        Node<DataType> *nodeIndex;//所在的结点
        int index;  //在结点中的关键字序列号
    };
    typedef struct SearchResult<DataType> SearchResult<DataType>;
    SearchResult<DataType> * searchNode(Node<DataType> *node,DataType key);
};

/**b树的搜索
 如果搜索成功，返回所找到的关键字所在的结点地址和关键字序列的有序对
 用结构体searchresult表示
 */
template <typename DataType>
SearchResult<DataType> * BTree<DataType>::searchNode(Node<DataType> *node, DataType key) {
    
    SearchResult<DataType> *srP;
    int i = 0;
    while (i < node->Key_Num && key > node->keyArray[i]) {
        i++;    //在结点中循环比较关键字
    }
    if (i < node->Key_Num && key == node->keyArray[i]) {
        //如果key在该结点中，则返回结点指针和关键字序列
        srP = (SearchResult<DataType> *)malloc(sizeof(struct SearchResult<DataType>));
        srP->nodeIndex = node;
        srP->index = i;
        return srP;
    }
    if (node->isLeaf) { // 如果key不在该结点中，且结点为叶子结点则返回null
        return NULL;
    }else
    {
        return searchNode(node->pChild[i], key);
    }
}

#endif /* BTree_hpp */
